import java.util.Arrays;

/*
 * @lc app=leetcode.cn id=684 lang=java
 *
 * [684] 冗余连接
 */

// @lc code=start
class Solution {
    //怪不得用并查集，一旦一道边加进来后发现成环，直接删去此边即可。
    public int[] findRedundantConnection(int[][] edges) {
        UnionFind uf = new UnionFind(edges.length);
        for(int[] edge : edges){
            if(!uf.union(edge[0], edge[1]))
                return edge;
        }
        return new int[0];
    }

    class UnionFind{
        private int[] parent;//记录父节点
        private int[] weight;//代表这个联通分量内节点的数目

        public UnionFind(int lenght){
            this.parent = new int[lenght+1];//这里要+1，因为输入的数字是从1开始顺序输入的。
            this.weight = new int[lenght+1];
            for(int i =0;i<lenght+1;i++){
                parent[i]=i;//父节点先令其等于本身
            }
            Arrays.fill(weight, 1);
        }
        public int find(int x){
            if(x!=parent[x]){
                parent[x] = find(parent[x]);//路径压缩，经过路径压缩后联通分量内所有节点指向父节点了
                // find(parent[x]);//这么写是不压缩的。
            }
            return parent[x];
        }
        public boolean union(int x ,int y){//合并x,y到一个联通分量
            int parentX = find(x);
            int parentY = find(y);
            //先拿到x,y的父节点
            if(parentX!=parentY){//证明x,y不在一个联通分量里，需要合并
                if (weight[parentX] < weight[parentY]) {//看那方节点多,多的那个变成fx
                    int temp = parentX;
                    parentX = parentY;
                    parentY = temp;
                }
                weight[parentX] += weight[parentY];
                parent[parentY]=parentX;//让parentX成为父节点，其实这个理论上应该是谁的子节点多谁当父节点的。
                return true;
            }
            //证明x,y在一个联通分量里，是没必要合并的，也就是多余的那个。合并了会变成环。
            return false;
        }
    }
}
// @lc code=end

